package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-22 23:07
 */
public class Pro0920 {
    public int numMusicPlaylists(int N, int L, int K) {
        //f[i][j] 表示播放列表长度为i，刚好有j首不同的个的播放列表数量
        long[][] dp = new long[L+1][N+1];
        dp[0][0] = 1;
        for(int i = 1; i <= L; i++) {
            for(int j =1; j <= N; j++) {
                dp[i][j] += dp[i-1][j-1] * (N - j + 1); //第j首歌未放过的
                dp[i][j] += dp[i-1][j] * Math.max(0, j - K);//第j首歌先前放过
                dp[i][j] %= 1_000_000_007;
            }
        }
        // for(int i = 0; i <= L; i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        return (int)dp[L][N];
    }
}
